The communications and computer industries are rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). A ternary CAM (TCAM) is a special type of fully associative memory which stores data with three logic values: ‘0’, ‘1’ or ‘*’ (don't care). Each TCAM entry includes a value and a mask. These entries are stored in the TCAM in decreasing order of priority, such as in a decreasing order of the length of prefixes. For a given input, the TCAM compares it against all of the entries in parallel, and returns the entry with the highest priority that matches the input lookup word. An entry matches the input lookup word if the input and the entry value are identical in the bits that are not masked out. A TCAM provides a fast mechanism for performing a longest matching prefix of a particular value, but natively does not provide a mechanism for directly performing operations on ranges.
In performing packet classification, a determination is often made whether a field of a packet matches a range of values. For example, a router may need to filter or only allow packets having a source or destination port number within a particular range of port numbers. Especially when processing packets, this operation typically needs to be performed very efficiently at typically at a line speed rate. Another application that typically relies on range search operations includes coordinating access to computer-readable medium, such a disk or memory. In this exemplary application, the processing of the packet or data may be limited by the rate at which a range operation is performed.
Additionally, sorting and range search problems are commonly encountered in several other applications, including the general locking problem. For example, in a distributed storage networking environment, many devices might be accessing shared data at very high speeds. These accesses are typically protected by locking the address range being accessed, with each specific location checked to see if it available or is already being accessed by another device before it can be accessed for certain functions. More generally, before locking a range, a check should be made to see if any address in the range overlaps with ranges being accessed by other devices. These sets of ranges changes dynamically as new locks are added and old ones are released. Other high speed applications of locking include memory protection, time range locks, SCSI reserve in a multi-host environment, locking memory accesses between processes, and locking accesses to a shared memory in case of multiprocessor environments. Range search is also useful in memory management to ensure that processes access only the allocated ranges of memory.
The demand on mechanisms for identifying a matching range and its use is changing as new applications are developed, especially with increasing processing rates and volume of range operations performed on a dynamic set of ranges. In the computing works, sorting and priority queue operations are commonly encountered and need to be performed at high speeds. Needed are methods and apparatus for maintaining sets of ranges and for determining a matching range based on a query point or query range.